package com.explorati.LeetCode92.reverseLinkedList2;

/**
 * 92. Reverse Linked List II 设立虚拟头节点+多设立指针记录值。然后根据逻辑解除
 * 
 * Reverse a linked list from position m to n. Do it in one-pass.
 * 
 * Input: 1->2->3->4->5->NULL, m = 2, n = 4
 * 
 * Output: 1->4->3->2->5->NULL
 * 
 * @author explorati
 *
 */
public class Solution {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

	public ListNode reverseBetween(ListNode head, int m, int n) {
		if (head == null) {
			return null;
		}
		if (head.next == null) {
			return head;
		}

		ListNode dummyHead = new ListNode(-1);
		dummyHead.next = head;
		ListNode pre = dummyHead;
		int num = 0;
		ListNode cur = head;
		while (num < m - 1) {
			pre = pre.next;
			cur = cur.next;
			num++;
		}
		ListNode begin = pre;

		ListNode last = cur;
		while (m - 1 <= num && num <= n - 1) {
			ListNode next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
			num++;
		}

		last.next = cur;
		begin.next = pre;

		return dummyHead.next;
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		ListNode head = s.new ListNode(1);
		ListNode cur = head;
		for (int i = 2; i <= 5; i++) {
			cur.next = s.new ListNode(i);
			cur = cur.next;
		}

		ListNode test = head;
		while (test != null) {
			System.out.print(test.val);
			if (test.next != null) {
				System.out.print("->");
			}
			test = test.next;
		}

		System.out.println();

		ListNode reverseListHead = s.reverseBetween(head, 2, 4);
		while (reverseListHead != null) {
			System.out.print(reverseListHead.val);
			if (reverseListHead.next != null) {
				System.out.print("->");
			}
			reverseListHead = reverseListHead.next;
		}
	}
}
